# 1 遍历
class Solution:
    def jumpFloorII(self, n):
        # write code here
        if n == 0 or n ==1:
            return 1
        res = [1,1,2]
        for i in range(3, n+1):
            for j in range(i, n+1):
                res[i] += res[j]
        return res[n+1]
# 2 省点儿内存
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, n):
        # write code here
        if n == 0 or n ==1:
            return 1
        prev1 = 1
        for i in range(2,n+1):
            res = prev1<<1
            prev1 = res
        return res
# 3 总结一下就是平方~~
'''
每个台阶都有跳与不跳两种情况（除了最后一个台阶），
最后一个台阶必须跳。所以共用2^(n-1)中情况
'''
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, n):
        # write code here
        if n == 0 or n ==1:
            return 1
        return pow(2,n-1)